import java.util.Arrays;

//堆：完全二叉树，顺序存储（数组）优先级队列，以层序遍历放置
//根结点的值小于孩子节点的的值，称为小根堆
//根节点大于左右节点，称为大根堆
class TestHeap{
     public int [] elem;
     int useSize;

    public TestHeap() {
        this.elem = new int [10];
    }
    public void init(int [] array){
        for (int i = 0; i < array.length; i++) {
            elem[useSize]=array[i];
            useSize++;
        }
    }
    //把数组的数据调整为大根堆
    private void swap(int c,int p){
        int tmp=elem[p];
       elem[p]=elem[c];
       elem[c]=tmp;
    }
    private void siftDown(int parent ,int end){
        int child=2*parent+1;
        while (child<useSize) {
            if (child + 1 < useSize && elem[child] < elem[child + 1]) {
                child++;
            }
            if (elem[child] > elem[parent]) {
                swap(child, parent);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }

    }
    //时间复杂度为n-log2(n+1)约等于n
    public void createHeap(){
        for (int parent = (useSize-1-1)/2; parent >=0 ; parent--) {
            siftDown(parent,useSize);
        }
    }
    public void createHeapS(){
        for (int parent = (useSize-1-1)/2; parent >=0 ; parent--) {
            int child=2*parent+1;
            while (child<useSize){
                if (child+1<useSize&&elem[child]>elem[child+1]){
                    child++;
                }
                if (elem[child]<elem[parent]){
                    swap(child,parent);
                    parent=child;
                    child=parent*2+1;
                }else {
                    break;
                }
            }
        }
    }
    //时间复杂度n*log2(n)
    private void siftUp(int child){
        int parent=(child-1)/2;
        while (parent>0){
            if (elem[child]>elem[parent]){
                swap(child,parent);
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
    }
    public boolean isFull(){
        return useSize==elem.length;
    }
    public void offer(int val){
        if (isFull()){
            elem= Arrays.copyOf(elem,elem.length*2);
        }
        elem[useSize]=val;
        useSize++;
        int child=useSize-1;
        siftUp(child);

    }
    private boolean isEmpty(){
        return useSize==0;
    }
    public int poll(){
        if (isEmpty()){
            return -1;
        }
        int old=elem[0];
        swap(0,useSize-1);
        useSize--;
        siftDown(0,useSize);
        return old;
    }
    //堆排序
    public void heepSort(){
        int endIndex=useSize-1;
        while (endIndex>0){
            swap(0,endIndex);
            siftDown(0,endIndex);
            endIndex--;
        }
    }//时间复杂度O（n*log2（n））

}
public class Text1 {
    public static void main(String[] args) {
        int []array=new int[]{27,15,19,18,28,34,65,49,25,37};
        TestHeap testHeap=new TestHeap();
        testHeap.init(array);
        testHeap.createHeap();

    }

}
